package leetcode_41_60;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class groupAnagrams_49 {
    /*
     *  字母异位词 组合在一起。可以按任意顺序返回结果列表。
     *  字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
     *  strs[i] 仅包含小写字母
     *
     * 603ms
     * 太慢了
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        /*
         即含有完全相同字符的分为一组
         例如
         ["eat", "tea", "tan", "ate", "nat", "bat","",""]
         分成四部分
         ["bat"],
         ["",""],
         ["nat","tan"],
         ["ate","eat","tea"]
         */
        List<List<String>>ans=new ArrayList<>();
        int []arr=new int[strs.length];   //默认值是0，如果为1，说明该字符串已经被添加，无需再比较
        for(int i=0;i<strs.length;i++){
            if(arr[i]==1)
                continue;
            List<String>one=new ArrayList<>();
            one.add(strs[i]);
            for(int t=i+1;t<strs.length;t++){
                if(arr[i]==1 || strs[i].length()!=strs[t].length())  //已被占用或者长度不想等直接跳过
                    continue;
                else if(isSameStr(strs[i],strs[t])){
                    one.add(strs[t]);
                    arr[t]=1;
                }
            }
            ans.add(one);
        }
        return ans;
    }
    /**
     * 判断两个长度相同的字符串是否是字母异位词
     */
    public boolean isSameStr(String a,String b){
        if(a.equals("")){
            return b.equals("");  //a是“”，b也是“”，,返回真，否则假
        } else if (b.equals(""))   //a不是“”，b是，假
            return false;
        //维护一个大小26的数组
        int [] arr=new int[26];  //数组默认值是0
        for(int i=0;i<a.length();i++){
            arr[a.charAt(i)-'a']+=1;    //遍历一个a的字母，数量加1
            arr[b.charAt(i)-'a']-=1;     //遍历一个b的字母，数量减1
        }
        for(int i=0;i<arr.length;i++)
            if(arr[i]!=0)
                return false;
        return true;
    }

    /*
    官解思路
    先将字符串排序，利用hashMap中
    键为排序后的字符串，值就为匹配的所有原始字符串集合
     */
    public List<List<String>> groupAnagrams2(String[] strs) {
        HashMap<String,List<String>>hash=new HashMap<>();
        for(String s:strs){
            char[] arr= s.toCharArray();
            Arrays.sort(arr);
            String key=new String(arr);
            List<String> list = hash.getOrDefault(key, new ArrayList<String>());      //有key对应的值就返回，没有返回指定的集合
            list.add(s);
            hash.put(key, list);
        }
        return new ArrayList<List<String>>(hash.values());
    }
}
